import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
//        char[][] grid = {
//                {'1', '1', '1', '1', '0'},
//                {'1', '1', '0', '1', '0'},
//                {'1', '1', '0', '0', '0'},
//                {'0', '0', '0', '0', '0'}
//        };
//        System.out.println(s.numIslands(grid));
        int[][] p = new int[][]{{0,1}};
        System.out.println(s.canFinish(2,p));
    }

    public int numIslands(char[][] grid) {
        /**
         * 岛屿数量
         *  之前我做过这道题，是使用BFS-洪水灌溉算法进行实现的，现在我尝试使用并查集进行实现
         *  这类题也是并查集的一个重要实现，即 给二维数组一位编号，对其进行并查集操作（因为并查集只能查询一维数组）*/
        // 1 预处理
        // -行、列、1的数量
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        for(int i = 0; i < m; i++) {
            for(int e: grid[i]) {
                if(e == '1') {
                    count ++;
                }
            }
        }
        // - 初始化并查集
        initialize(m*n);

        // 2 循环合并
        for(int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // -不越界访问
                // -仅在当前值为1时才进行后续操作
                if(grid[i][j] == '1') {
                    int lastUp = (i - 1) * n + j;
                    int lastLeft = i * n + j - 1;
                    int current = i * n + j;
                    if (i == 0) {
                        lastUp = -1;
                    }
                    if (j == 0) {
                        lastLeft = -1;
                    }
                    // -合并（不用判断是否在一个集合，因为合并时会判断）
                    if (lastUp >= 0 && grid[i - 1][j] == '1') {
                        union(current, lastUp);
                        count--;
                    }
                    // -第二个合并必须判断是否属于一个集合，因为在第一合并时可能就是一个集合
                    if (lastLeft >= 0 && grid[i][j - 1] == '1' && !isSameSet(current, lastLeft)) {
                        union(current, lastLeft);
                        count--;
                    }
                }
            }
        }

        // 3 返回值
        return count;
    }

    // 准备并查集
    public static int MAX_N = 0;
    public static int[] father = new int[MAX_N];
    public static int[] size = new int[MAX_N];
    public static int[] stack = new int[MAX_N];

    public static void initialize(int n) {
        /**
         * 初始化*/
        MAX_N = n;
        father = new int[MAX_N];
        size = new int[MAX_N];
        stack = new int[MAX_N];
        for(int i = 0; i < MAX_N; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 找到元素a所在集合的代表元素*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合*/
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                size[fb] = -1;
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                size[fa] = -1;
                father[fa] = fb;
            }
        }
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断两个元素是否属于一个集合*/
        return find(a) == find(b);
    }

    public boolean canFinish(int n, int[][] p) {
        /**
         * 课程表Ⅰ
         *  拓扑排序算法练习*/
        // 1 预处理
        // -入度表
        int[] inEdges = new int[n];
        // -建图
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0; i < p.length; i++) {
            if(!map.containsKey(p[i][1])) {
                map.put(p[i][1], new ArrayList<>());
            }
            map.get(p[i][1]).add(p[i][0]);
            // -更新入度
            inEdges[p[i][0]] ++;
        }
        // -准备队列并初始化
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            // -若是课程入度为0，加入课程
            if(inEdges[i] == 0) {
                queue.offer(i);
            }
        }

        // 2 开始拓扑排序
        while(!queue.isEmpty()) {
            // -1 出队
            int cur = queue.poll();
            // -2 更新入度
            for(int e: map.getOrDefault(cur, new ArrayList<>())) {
                inEdges[e] --;
                // -3 将入度为0入队
                if(inEdges[e] == 0) {
                    queue.offer(e);
                }
            }
        }

        // 3 判断是否有环
        for(int e: inEdges) {
            if(e != 0) {
                return false;
            }
        }
        return true;
    }
}
